/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2019年11月17日
*   版    本：v1.0.0
*   描    述：
*   Copyright (C) 2019 All rights reserved.
*   
* ================================================================*/


#include <iostream>
#include <stack>
#include <deque>
using namespace std;

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    TreeNode* addOneRow(TreeNode* root, int v, int d) {
        if(d == 1){
            TreeNode* newhead = new TreeNode(v);
            newhead->left = root;
            return newhead;
        }

        insert(root, 1, d, v);
        return root;
    }

    void insert(TreeNode* root, int depth, int d, int val){
        if(!root){
            return;
        }

        if(depth == d - 1){
            TreeNode* leftnode = new TreeNode(val);
            leftnode->left = root->left;
            root->left = leftnode;

            TreeNode* rightnode = new TreeNode(val);
            rightnode->right = root->right;
            root->right = rightnode;
        }else{
            insert(root->left, depth+1, d, val);
            insert(root->right, depth+1, d, val);
        }
    }
};

class Solution {
public:
    TreeNode* addOneRow(TreeNode* root, int v, int d) {
        if(d == 1){
            TreeNode* newhead = new TreeNode(v);
            newhead->left = root;
            return newhead;
        }

        insert(root, d, v);
        return root;
    }

    void insert(TreeNode* root, int d, int val){
        deque<TreeNode*>q;
        int depth = 1;
        TreeNode *p = NULL;
        q.push_back(root);        
        while(depth < d-1 && !q.empty()){
            int size = q.size();
            while(size > 0){
                p = q.front();
                q.pop_front();
                if(p->left){
                    q.push_back(p->left);
                }
                if(p->right){
                    q.push_back(p->right);
                }
                size--;
            }

            depth++;
        }

        while(!q.empty()){
            p = q.front();
            q.pop_front();

            TreeNode* leftnode = new TreeNode(val);
            leftnode->left = p->left;
            p->left = leftnode;

            TreeNode* rightnode = new TreeNode(val);
            rightnode->right = p->right;
            p->right = rightnode;
        }

        return;
    }
};